/**
 * @file
 * @brief   二叉树，二叉链表方式.
 * @details  基本功能演示.
 * @author   conkty@126.com
 * @date    2023
 * @version  v0.1
 * @par 更新记录:
 *	v0.1: 初建\n
 */
#include <assert.h>
#include <stdio.h>
#include <stdlib.h>

// 树的结点声明
typedef struct BiNode {
  int data;
  struct BiNode *left;  // 左孩子
  struct BiNode *right; // 右孩子
} Node, *BiTree;        // 注意: BiTree 实质是 Node* (即 BiNode* ) 类型

/** 创建二叉树, 递归, 交互式
 * @param T 树的地址的地址, 实际是BiNode**类型. 
        BiNode*是树的地址，但这里，树直接在里面创建，地址要通过T返回出去，故需加一层*.
 */
void create_tree(BiTree *T) {
  // 结点数据的输入
  int data;
  printf("\ninput: ");
  scanf("%d", &data);

  // 输入标记值，表示该结点为空. 这个分支到此结束.
  if (-1 == data)
    *T = NULL;

  else {
    // 创建新结点，其地址将向外传递
    *T = (Node *)malloc(sizeof(Node));
    // 应操作T里的地址, 而不是T本身的地址. 为方便, 定义一个临时指针,
    // 指向T的内容(地址)
    Node *p = *T;
    assert(NULL != p);

    // 当前结点赋值(该结点是其子树的根)
    p->data = data;
    // 测试用, 可以关闭
    // printf("input data is %d ", p->data);

    // 创建p的左子树
    create_tree(&(p->left));
    // 创建p的右子树
    create_tree(&(p->right));
  }
}

/**
 * @brief 创建二叉树, 递归, 批量式
 *  为方便调试或更方便使用, 实现第二种创建树的函数,直接基于现成的数组进行。
 *  其中为了方便在递归中遍历数组，函数内采用了static语法，注意理解。
 * @param T 树的地址的地址, 理由同上.
 * @param inputs 预先准备的结点数据序列.
 */
void create_tree_by_array(BiTree *T, int inputs[]) {
  static int i = 0; // 数组的索引, 初始化(函数第一次调用时)为0.
  // 结点数据的输入
  int data = inputs[i];
  printf("\ninput %d: %d ", i, data);

  ++i; // 随着递归的进行，累加数组索引.

  // 输入标记值，表示该结点为空. 这个分支到此结束.
  if (-1 == data)
    *T = NULL;

  else {
    // 创建新结点，其地址将向外传递
    *T = (Node *)malloc(sizeof(Node));
    // 应操作T里的地址, 而不是T本身的地址. 为方便, 定义一个临时指针,
    // 指向T的内容(地址)
    Node *p = *T;
    assert(NULL != p);

    // 当前结点赋值(该结点是其子树的根)
    p->data = data;
    // 测试用, 可以关闭
    // printf("input data is %d ", p->data);

    // 创建p的左子树
    create_tree_by_array(&(p->left), inputs);
    // 创建p的右子树
    create_tree_by_array(&(p->right), inputs);
  }
}

/** 先序遍历
* @param T 根结点(包括各层子树的)地址
由于只是读取数据, 故不再需要两层*, BiTree类型即可.
*/
void traverse_DLR(BiTree T) {
  // 为方便核验序列, 方便测试, 若T结点为空, 在输出的序列中打印为标记符号 #.
  if (NULL == T) {
    printf(" #");
    return;
  } else {
    printf(" %d", T->data);
    traverse_DLR(T->left);
    traverse_DLR(T->right);
  }
}

int main() {
  /*  为方便验证代码实现的正确性，先采用书中的数据，以数字代替其中的字母：
     A, B, C, D, E, F, G, # 依次变为: 1, 2, 3, 4, 5, 6, 7, -1.
     于是，书中序列“A B C # # D E # G # # F # # #”
     应变成“1 2 3 -1 -1 4 5 -1 7 -1 -1 6 -1 -1 -1”

     通过键盘交互式构建这个树时，对于上面的代码，应依次输入后面这个数字串。
     构建完成后，调用先序（前序）遍历函数，应输出如下结果（遍历序列）：
     “1 2 3 # # 4 5 # 7 # # 6 # # #”
     
     如此，构建的输入顺序与遍历的输出序列对照，若一致，说明代码实现无错。
  */
  // ！！！注意：针对实验报告，所准备的数组数据或交互式输入的数据应该更换。
  int inputs[] = {1, 2, 3, -1, -1, 4, 5, -1, 7, -1, -1, 6, -1, -1, -1};

  BiTree t = NULL;
  create_tree_by_array(&t, inputs);

  printf("\nThe tree is created.\n");
  printf("Data of Tree in DLR order are: \n");

  traverse_DLR(t);

  // 也可以尝试人工交互式创建
  /*
  BiTree t2 = NULL;
  create_tree(&t2);

  printf("\nThe tree is created.\n");
  printf("Data of Tree in DLR order are: \n");

  traverse_DLR(t);
  */

  return 0;
}